Resource allocation is an important issue in many applications, including networking, distributed computing and software testing. Resource allocation in general involves an environment having resources that are pooled and allocated to a process to satisfy its needs. “Batch resource allocation” occurs when multiple processes contend for a pool of resources and is often encountered in the context of distributed computing or automated testing.
A material constraint of the batch resource allocation problem is that, while resources can be reused across different processes, they are subject to mutually exclusive use among the concurrent steps of any individual process. As a result, optimizing the general batch resource allocation problem is NP-hard, which implies that an efficient (polynomial time) method for finding the exact optimum solution is unlikely to exist. The proper management of batch resource allocation typically reduces the resource management (e.g., setup) costs for the environment and allows more processes to share the pool of resources simultaneously. Unfortunately, while batch resource allocation can provide substantial benefits, efforts to date have instead focused on allocation of resources with respect to a single (parallel or distributed) process, in which resources aren't reused.
For instance, in distributed or “grid” computing, users reserve resources with certain characteristics (e.g., machines with more than 1 GB memory) for high-demand parallel computations. Protocols, such as the well-known Condor-G Matchmaking protocol, are used to specify various constraints on resource properties for a single process. In the networking community, test beds such as PlanetLab (a large-scale distributed environment) have been developed to encourage designing and experimenting new networking protocols (e.g., application-level multicast). Systems such as Plush provide a user shell that helps users manage applications and resources on PlanetLab. All these systems support resource allocation and reservation only for single processes.